mullersmethodfandomcom-20200214-history
Muller's Method
Müller's method is a root-finding algorithm, a numerical method for solving equations of the form f''(''x) = 0. It is first presented by D. E. Müller in 1956. Müller's method is based on the secant method]], which constructs at every iteration a line through two points on the graph of f''. Instead, Müller's method uses three points, constructs the parabola]] through these three points, and takes the intersection of the x-axis|''x-axis with the parabola to be the next approximation. It is a technique for finding the root of a scalar-valued function f(x) of a single variable x when no information about the derivative exists. It is a generalization of the secant method, but instead of using two points, it uses three points and finds an interpolating quadratic polynomial. This method is better suited to finding the roots of polynomials, and therefore we will focus on this particular application of Müller's method. Recurrence relation The three initial values needed are denoted as x''k'', x''k''-1 and x''k''-2. The parabola going through the three points (x''k'', f''(''xk'')), (''xk''-1, ''f(x''k''-1)) and (x''k''-2, f''(''xk''-2)), when written in the |Newton form, is : y = f(x_k) + (x-x_k) fx_{k-1} + (x-x_k) (x-x_{k-1}) fx_{k-1}, x_{k-2}, \, where ''f[x''k'', x''k''-1] and f''[''xk'', ''xk''-1, ''xk''-2] denote divided differences. This can be rewritten as : y = f(x_k) + w(x-x_k) + fx_{k-1}, x_{k-2} \, (x-x_k)^2 \, where : w = fx_k,x_{k-1} + fx_k,x_{k-2} - fx_{k-1},x_{k-2}. \, The next iterate is now given by the root of the quadratic equation ''y = 0. This yields the recurrence relation : x_{k+1} = x_k - \frac{2f(x_k)}{w \pm \sqrt{w^2 - 4f(x_k)fx_{k-1}, x_{k-2}}}. In this formula, the sign should be chosen such that the denominator is as large as possible in magnitude. We do not use the standard formula for solving quadratic equations because that may lead to loss of significance. Note that x''k''+1 can be complex, even if the previous iterates were all real. This is in contrast with other root-finding algorithms like the secant method or Newton's method, whose iterates will remain real if one starts with real numbers. Having complex iterates can be an advantage (if one is looking for complex roots) or a disadvantage (if it is known that all roots are real), depending on the problem. Speed of convergence The rate of convergence of Müller's method is approximately 1.84. This can be compared with 1.62 for the secant method and 2 for Newton's method. So, the secant method makes less progress per iteration than Müller's method and Newton's method makes more progress. More precisely, if ξ denotes a single root of f'' (so ''f(ξ) = 0 and f'(ξ) ≠ 0), f'' is three times continuously differentiable, and the initial guesses ''x''0, ''x''1, and ''x''2 are taken sufficiently close to ξ, then the iterates satisfy : \lim_{k\to\infty} \frac {|x-x_{k-1}|^p} = \left| \frac{f'(\xi)}{6f'(\xi)} \right|^{(p-1)/2}, where p'' ≈ 1.84 is the positive root of x^3 - x^2 - x - 1 = 0 . Example Example of Muller's Method Implementation (in C Programming Language) #include #include #include #include #include main() { //clrscr(); double x=0, x0=0, x1=0, x2=0, tol=0; double fx=0, fx0=0, fx1=0, fx2=0, h0=0, h1=0, h2=0, a=0, b=0, c=0; int i=0, numloops=0, maxloops=100; double Discriminant=0, x3=0, xroot=0, xroot1=0, xroot2=0, r1=0, r2=0; printf("\n\t "); printf("\n\t\tMuller's Method"); printf("\n\t "); printf("\n\nFinding the root of the equation: F(X) = x^3 - 5x^2 + 4x"); // EQUATION printf("\n\nInput a initial value for x0: "); printf("Input a initial value for x1: "); printf("Input a initial value for x2: "); printf("Set the Tolerance: "); do{ //Evaluate Function Values do{ switch(i) { case 0: x=x0; break; case 1: x=x1; break; case 2: x=x2; break; } fx=pow(x,3)-5*pow(x,2)+4*x; // EQUATION : F(X) = x^3 - 5x^2 + 4x switch(i) { case 0: fx0=fx; break; case 1: fx1=fx; break; case 2: fx2=fx; break; } i++; }while(i<=2); // Reset values to new parabola h0=x0-x2; h1=x1-x2; h2=h0*h1*(h0-h1); // Find coefficients of parabola a = ((h1*(fx0-fx2))-(h0*(fx1-fx2)))/h2; b = ((pow(h0,2)*(fx1-fx2))-(pow(h1,2)*(fx0-fx2)))/h2; c = fx2; // Compute the Discriminant of the quadratic Discriminant= sqrt ((b*b)-(4*a*c)); //Compute Roots r1= b+Discriminant; r2= b-Discriminant; xroot1 = x2-((2*c)/r1); xroot2 = x2-((2*c)/r2); // Choose Roots by picking the closer distance to xroot if(fabs(r1) >= fabs(r2)) xroot=xroot1; else xroot=xroot2; // Rearrange the roots x0=x1; x1=x2; x2=xroot; x=xroot; fx=pow(x,3)-5*pow(x,2)+4*x; // EQUATION : F(X) = x^3 - 5x^2 + 4x //Display Values printf("\n\n\n"); if(numloops!=0) printf("\nIteration no. %d:\n", numloops); printf("\nValues:\n"); printf("\nfx0: %lf \nfx1: %lf \nfx2: %lf\n", fx0, fx1, fx2); printf("\na: %lf \nb: %lf \nc: %lf\n", a, b, c); printf("\nRoot:%lf \nf(Root):%lf\n", xroot,fabs(fx)); numloops++; }while ((fabs(fx)>=tol) && (numloops <= maxloops)); // Check to determine whether the root was found or there was an error in the computation.. if ( fabs(fx) > tol ) printf("\nError in computing the root of the function!"); else if(numloops >= maxloops) printf("\nExceeded the maximum number of iterations!"); else printf("\n\n\n\nThe root of the function is %lf ", xroot); numloops = 0; getch(); } Application to Engineering As for the application, finding the roots of a polynomial are necessary when determining the behaviour and stability of a linear system. One example of these is the application of Muller's Method to Photoelasticity. The essence of the Muller method is that the light beam and the optical device (polaroid, phase plate, photoelastic material of the model) can be represented in matrix form in such a way that the results of the polarization light transformations can be computed simply by multiplying these matrices. Thus, if the optical device is described by the matrix U and the incoming and outgoing light beams by the matrices A(O) and A, then A = UA(O). Muller's method can also be adapted to allow quantitative characterization of the affinity and cross-reactivity of antibodies by competitive radioimmunoassay. References * Muller, David E., "A Method for Solving Algebraic Equations Using an Automatic Computer," MTAC, 10 (1956), 208-215. * Atkinson, Kendall E. (1989). ''An Introduction to Numerical Analysis, 2nd edition, Section 2.4. John Wiley & Sons, New York. ISBN 0-471-50023-2. * Burden, R. L. and Faires, J. D. Numerical Analysis, 4th edition, pages 77ff. * Press, William H., et al. (1992). Numerical Recipes]] in Fortran 77: The Art of Scientific Computing, 2nd edition, page 364. ISBN 052143064X. External links *Module for Muller's Method by John H. Mathews *Müller's Method (find a complex root of an analytic function) *Numerical Analysis for Engineering *Application of Muller's method to Photoelasticity *Adaptation of the Müller method to allow quantitative characterization of the affinity and cross-reactivity of antibodies by competitive radioimmunoassay